A.: Analysis of “hiring above the median”: a “Lake Wobegon” strategy for the hiring problem

The hiring problem is a recent research problem, which has been introduced and studied first by Broder et al. [2] in 2008. It belongs to the category of on-line decision making under uncertainty. In such kind of research, the input is a sequence of instances and a decision must be taken for each instance depending on the instances seen so far while no information on the future is available. The hiring problem can be considered as a natural extension of the well-known secretary problem [3], where the employer is now looking for many candidates rather than only one (as it is the case for the secretary problem). Here the goal is to design some hiring strategy to meet the demands of the employer, which essentially are to obtain a good quality staff at a reasonable hiring rate. Broder et al. introduced two so-called “Lake Wobegon strategies”, namely “hiring above the current mean ” and “hiring above the current median”, applied for a continuous probabilistic model for the sequence of scores of the candidates. Archibald and Mart́ınez [1] have reformulated the problem for a discrete model that considers the relative ranks amongst candidates as it is the case in the secretary problem. For this model in [1] the authors studied two general strategies, namely “hiring above the m-th best candidate”, and “hiring above the median” (and other quantiles). In this work we give a detailed study of the “hiring above the median ” strategy under this discrete model for the input sequence of scores of ∗This work started when the first author was visiting th